package com.wtgroup.demo.leetcode.q060_排列序列_第k个排列;

/**
 * LC官方解, 方法一：数学 + 缩小问题规模
 */
public class Q060_LC_1 {

    /*
    执行用时：6 ms , 在所有 Java 提交中击败了 37.79% 的用户
    内存消耗： 35.7 MB , 在所有 Java 提交中击败了 83.63% 的用户
    */

    public String getPermutation(int n, int k) {
        // 为了高效, 提前计算好阶乘 (n-1)!
        int[] factorial = new int[n+1];
        factorial[0] = 1;
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i-1] * i;
        }

        boolean[] used = new boolean[n+1];
        StringBuilder ans = new StringBuilder(n);

        // 自左到右, 逐个确定该用什么数字(尽可能最小的). 确定组序号, 还剩下的, 继续.
        // 神奇的数学规律
        k = k-1;
        for (int i = 1; i <= n; i++) {
            int order = k / factorial[n-i] + 1;
            /*
            * 最小的极限取 order 大小的数字, 但考虑到可能有被使用的. 从1开始计数, 没用过的计数, 直到达到 order 停止
            * 我这里必LC官方解得处理方式好理解点.
            * */
            int cnt = 0;
            for (int j = 1; j <= n; j++) {
                if (!used[j]) {
                    cnt++;
                }
                if (cnt==order) {
                    ans.append(j+"");
                    used[j] = true;
                    break;
                }
            }
            // n-i 规模上继续
            k = k % factorial[n - i];
        }
        return ans.toString();
    }

}
